package com.leetcode.二叉树.深度优先.迭代遍历;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;


/**
 * 遍历顺序：
 *	前序遍历：中->左->右
 *	中序遍历：左->中->右
 *	后序遍历：左->右->中
 * 二叉树的迭代遍历算法是利用栈(stack)先进后出的特点，只有栈弹出的时候才算是访问，入栈只是保证访问顺序 
 * 
 *二叉树的每一个节点都可以看成是中间节点，只不过是有没有左右子树的区别而已。二叉树的所有遍历算法都是利用这个思想来实现的！！！！！！！！！
 */
public class 一般迭代算法 {
	/**
	 * 前序遍历
	 * 前序遍历是中左右，每次先处理的是中间节点，那么先将根节点放入栈中，然后开始循环处理，先将栈顶元素弹出判断，然后将右孩子加入栈，再加入左孩子。
	 * 为什么要先加入 右孩子，再加入左孩子呢？ 因为这样出栈的时候才是中左右的顺序。
	 */
	public List<Integer> preorderTraversal(TreeNode root) {
		List<Integer> result = new ArrayList<>();
		Deque<TreeNode> stack = new LinkedList<TreeNode>();
		if(root != null) stack.push(root);
		while(!stack.isEmpty()) {
			TreeNode node = stack.pop();//出栈
			result.add(node.val);
			//为什么这里右子树比左子树先入栈，因为根据stack先进后出的特点，stack弹出的时候，可以保证左子树先弹出
			if(node.right != null) stack.push(node.right);
			if(node.left != null) stack.push(node.left);
		}
		return result;
    }
	
	/**
	 * 中序遍历，中序遍历不能只是修改前序遍历的代码就可以完成。
	 * 为了解释清楚，我说明一下 刚刚在迭代的过程中，其实我们有两个操作：
	 * 处理：将元素放进result数组中
	 * 访问：遍历节点
	 * （处理和访问的顺序不一样，导致不能简单修改前序的算法）
	 * 分析一下为什么前序遍历的代码，不能和中序遍历通用呢，因为前序遍历的顺序是中左右，先访问的元素是中间节点，要处理的元素也是中间节点，所以才能写出相对简洁的代码，因为要访问的元素和要处理的元素顺序是一致的，都是中间节点。
	 * 那么再看看中序遍历，中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中），这就造成了处理顺序和访问顺序是不一致的。
	 * 那么在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。
	 * 																				A
	 * 思路：                 																   / \
	 * 用一个cur来表示当前的节点是要向下访问，还是处理，（访问和处理的解释见上面）                                                   B   C
	 * 以下题解中，我们需要记住每个节点的身份：二叉树的每一个节点都可以看成是中间节点，只不过是有没有左右子树的区别而已。
	 * cur不为空，则继续向下访问，为空，则处理栈顶的元素
	 * 1、cur先指向root
	 * 2、if(cur不为空),则继续向下访问，cur入栈，cur指向cur的左子树
	 * 3、if(cur为空) 则此时需要处理栈顶元素。以右边的树为例，A为root，A的左子树为B，A的右子树为C
	 * 则cur第一次出现null的情况是，cur指向B的左子树，因为一开始cur指向A，然后不断指向左子树，B也有左右子树，只不过为空而已。
	 * 此时我们将B看作是中间节点，那cur就是B的左子树，根据中序遍历，那么cur就要先输出，再输出B
	 * 因此我们把此时的cur当作是已经输出了（cur此时为null嘛，我们当作输出了，不把它放进result就行了），
	 * 接下来就是输出B，B在哪？B已经入栈了，而且B在栈顶，因此我们需要做的第一步就是：
	 * ①：cur指向B，也就是cur指向栈顶元素，然后出栈，输出B（在这里是将结果放进result中）
	 * ②：cur再指向cur的右子树，因为此时cur指向B，因为根据中序遍历，输出完B，就要输出B的右子树。
	 * cur为null，都是进行同样的操作。
	 */
	 public List<Integer> inorderTraversal(TreeNode root) {
		List<Integer> result = new ArrayList<>();
		Deque<TreeNode> stack = new LinkedList<TreeNode>();
		//用cur来标记当前的节点，如果cur不为空，则继续向下访问，如果cur为空，则处理栈顶的元素（访问和处理的解释见上面）
		TreeNode cur = root;
		while(cur != null || !stack.isEmpty()) {
			if(cur != null) {
				stack.push(cur);//cur不为空，就将cur入栈
				cur = cur.left;//继续向下访问，cur指向左子树
			}else {
				cur = stack.pop();
				result.add(cur.val);
				cur = cur.right;//cur指向右子树
			}
		}
		return result;
	 }
	 
	 /**
	  * 后序遍历
	  * 后序遍历就可以改改前序遍历的代码了，只需要将前序遍历的顺序改为：中->右->左
	  * 然后再将整个结果反转，就得到了：左->右->中
	  */
	 public List<Integer> postorderTraversal(TreeNode root) {
		List<Integer> result = new ArrayList<>();
		Deque<TreeNode> stack = new LinkedList<TreeNode>();
		if(root != null) stack.push(root);
		while(!stack.isEmpty()) {
			TreeNode node = stack.pop();//出栈
			result.add(node.val);
			//为什么这里左子树比右子树先入栈，因为根据stack先进后出的特点，stack弹出的时候，可以保证右子树先弹出
			if(node.left != null) stack.push(node.left);
			if(node.right != null) stack.push(node.right);
		}
		//以上得到的结果是：中->右->左，整体反转，得到：左->右->中
		Collections.reverse(result);
		return result;
	 }
}
